package com.sam.book;

public class LeftistHeap<T extends Comparable<? super T>> {

    private Node<T> root;

    public void insert(T t) {
        merge1(root, new Node<>(t));
    }
    public void merge(LeftistHeap<T> rhs) {
        if (this == rhs) {//不接受h.merge(h)
            return;
        }
        root = merge(root, rhs.root);
        rhs.root = null;
    }

    public T deleteMin() {
        if (isEmpty()) {
            return null;
        }
        T t = root.element;
        root = merge(root.left, root.right);
        return t;
    }

    public boolean isEmpty() {
        return root == null;
    }

    private Node<T> merge(Node<T> h1, Node<T> h2) {
        if (h1 == null) {
            return h2;
        } else if (h2 == null) {
            return h1;
        } else if (h1.element.compareTo(h2.element) < 0) {
            return merge1(h1, h2);
        } else {
            return merge1(h2, h1);
        }
    }

    private Node<T> merge1(Node<T> h1, Node<T> h2) {
        if (h1.left == null) {
            h1.left = h2;
        } else {
            h1.right = merge(h1.right, h2);
            if (h1.left.npl < h1.right.npl) {
                swapChild(h1);
            }
            h1.npl = h1.right.npl + 1;
        }
        return h1;
    }

    private void swapChild(Node<T> tNode) {
        final Node<T> left = tNode.left;
        tNode.left = tNode.right;
        tNode.right = left;
    }

    private static class Node<T> {
        T element;
        Node<T> left;
        Node<T> right;
        int npl;
        Node(T t) {
            this(t, null, null);
        }

        public Node(T element, Node<T> left, Node<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }


}